GiST

Na computação, GiST or Generalized Search Tree ou Árvore de busca genérica, é uma estrutura de dados e API que pode ser usada para construir quase todo tipo de árvore de busca sob quase todo tipo de dado. Com GiST é possível construir árvores B+, árvores kd, árvores hB, árvores RD, árvores R e muitas mais. Contudo, ela não pode ser usada para construir uma árvore de prefixos, apesar de poder dar suporte a outras formas de compressão, incluindo compressão lossy. GiST pode ser usada eficientemente para qualquer tipo de dados que possa ser naturalmente ordenado em uma hierarquia de conjuntos. Não é apenas extensível em termos de tipos de dados e layout de árvore, mas ela também permite árvores de busca pré-definidas personalizadas. GiST é implementado no banco de dados relacional PostgreSQL e também foi implementada como uma biblioteca, libgist.

GiST é bastante útil pois ela permite que novos índices, baseados em árvores, sejam criados facilmente. No PostgreSQL, o código da infra estrutura GiST gerencia o layout das próprias páginas de índice, os algoritmos para busca em índices e para remoção dos índices, e outros detalhes de implementação complexos, como trancamento para alta concorrência em nível de páginas de memória e write-ahead logging para recuperação de dados. Isto permite que os autores de novos índices baseados em árvores se foquem em implementar as novas características do novo tipo de índice.

Os desenvolvedores atuais(Oleg Bartunov e Teodor Sigaev) do GiST em PostgreSQL adicionaram o suporte para chaves de tamanho variáveis, chaves compostas e suporte para recuperação e concorrência, os quais foram automaticamente herdados por todas as extensões do GiST, como o PostGIS, busca full-text e outras.

Existem vários módulos que foram desenvolvidos usando GiST e distribuídos com o PostgreSQL. Por exemplo:

rtree_gist, btree_gist - implementação GiST das árvores R e B
intarray - Suporte a índices para um vetor unidimensional de int4s
tsearch2 - um tipo de busca(full text) com acesso indexado
ltree - tipos de dados, métodos de acesso indexado e busca para dados organizados como estruturas semelhantes a árvores
hstore - Armazenamento para dados do tipo (chave,valor)
cube - tipos de dados, representando cubos multidimensionais